from typing import *


class Solution:
    def maxTargetNodes(
        self, edges1: List[List[int]], edges2: List[List[int]]
    ) -> List[int]:

        def f(edges):
            m = len(edges) + 1
            next = [[] for _ in range(m)]
            for a, b in edges:
                next[a].append(b)
                next[b].append(a)

            dp = [[] for _ in range(m)]

            def g(p, n):
                dp[n] = [1, 0]
                for nxt in next[n]:
                    if nxt != p:
                        g(n, nxt)
                        dp[n][0] += dp[nxt][1]
                        dp[n][1] += dp[nxt][0]

            g(None, 0)
            ans = [[] for _ in range(m)]

            def h(p, n):
                ans[n] = [dp[n][0], dp[n][1]]
                for nxt in next[n]:
                    if nxt != p:
                        a, b = dp[n]
                        dp[n][0] -= dp[nxt][1]
                        dp[n][1] -= dp[nxt][0]
                        c, d = dp[nxt]
                        dp[nxt][0] += dp[n][1]
                        dp[nxt][1] += dp[n][0]
                        h(n, nxt)
                        dp[nxt] = [c, d]
                        dp[n] = [a, b]

            h(None, 0)
            return ans

        d1 = f(edges1)
        d2 = f(edges2)
        n = len(edges1) + 1
        mx = -1
        for i in range(len(edges2) + 1):
            mx = max(mx, d2[i][1])
        ans = [0] * n
        for i in range(n):
            ans[i] = d1[i][0] + mx
        return ans


s = Solution()
print(s.maxTargetNodes([[0, 1]], [[0, 1], [1, 2]]))
print(
    s.maxTargetNodes(
        edges1=[[0, 1], [0, 2], [2, 3], [2, 4]],
        edges2=[[0, 1], [0, 2], [0, 3], [2, 7], [1, 4], [4, 5], [4, 6]],
    )
)
print(
    s.maxTargetNodes(
        edges1=[[0, 1], [0, 2], [0, 3], [0, 4]], edges2=[[0, 1], [1, 2], [2, 3]]
    )
)
